package l.l.w.leetcode._140_WordBreakII;

import java.util.*;

/**
 * Created by llw on 2018/5/19/0019.
 */
public class _140_WordBreakII {
    public List<String> wordBreak(String s, List<String> wordDict) {
        LinkedList<String> result = new LinkedList<>();
        boolean[] f = new boolean[s.length()+1];
        f[0] = true;
        Map<Integer,List<String>> map = new HashMap<Integer, List<String>>();
        for(int i = 1; i <= s.length(); ++i){
            for(int j = 0; j < i; ++j){
                String substring = s.substring(j, i);
                if(f[j] && wordDict.contains(substring)){
                    f[i] = true;
                    if(map.get(j) != null){
                        map.get(j).add(substring);
                    }else{
                        LinkedList<String> list = new LinkedList<>();
                        list.add(substring);
                        map.put(j,list);
                    }
                }
            }
        }

        if(f[s.length()]){
//            StringBuffer sb = new StringBuffer();
            getResult(result, "", map, 0, s, f);
        }
        return result;
    }

    private void getResult(LinkedList<String> result, String one, Map<Integer, List<String>> map, int i,String s, boolean[] f) {
        if(i == s.length()){
//            sb.deleteCharAt(sb.length() - 1);
//            result.add(sb.toString());
            result.add(one.substring(0,one.length() - 1));
            return;
        }
        if(!f[i]) return;
        List<String> list = map.get(i);
        if(list == null) return;
        for(String str : list){
//            StringBuffer buffer = new StringBuffer(sb);
//            buffer.append(str);
//            buffer.append(" ");
//            getResult(result, buffer, map, i + str.length(), s);
            getResult(result,one + str + " ",map,i + str.length(), s,f);
        }
    }

    public boolean isWordBreak(String s, List<String> wordDict) {
        boolean[] f = new boolean[s.length()+1];
        f[0] = true;
        for(int i = 1; i <= s.length(); ++i){
            for(int j = 0; j < i; ++j){
                String substring = s.substring(j, i);
                if(f[j] && wordDict.contains(substring)){
                    f[i] = true;
                    break;
                }
            }
        }
        return f[s.length()];
    }

    public static void main(String[] args) {
        String s = "abcd";
        String[] ss = {"a","abc","b","cd"};
        List<String> dict = Arrays.asList(ss);
        _140_WordBreakII solution = new _140_WordBreakII();
        boolean result = solution.isWordBreak(s, dict);
        List<String> strings = solution.wordBreak(s, dict);
        System.out.println(result);
        System.out.println(strings);
    }
}
